
class Solution {
public:
	const int module = 1000000007;
    int numWays(int steps, int arrLen) {
        int min_j = min(steps,arrLen-1);
    	vector<vector<int>> f(steps + 1, vector<int>(min_j + 1)); 
        f[0][0]=1;
    	for(int i = 1; i <= steps; i++){
    		for(int j = 0; j <= min_j; j++){
    			f[i][j]=f[i-1][j];
    			if(j>=1) f[i][j] = (f[i][j]+f[i-1][j-1])%module;
    			if(j+1 <= min_j) f[i][j]=(f[i][j]+f[i-1][j+1])%module;
    		}
    	}
    	return f[steps][0];
    } 
};